/**
 * @file 094.最小回文分割.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-20
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution
{
public:
    int minCut(string s)
    {
        // dp[i] 表示前缀s[0:i]的最少分割次数
        // 当然如果s[0:i]本身就是一个回文串，dp[i]=0
        // dp[i]=枚举0到i min(dp[j])+1 其中s[j+1:i]是个回文串<-加1就加在这
        // 具体判断一个区间内的串是否回文比较费时，可以先打表
        // 先打表g[i][j] 表示[i,j]闭区间内的串是否回文
        int n = s.length();
        vector<vector<bool>> g(n, vector<bool>(n, false));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j]) {
                    if (i == j || i + 1 == j) {
                        g[i][j] = true;
                    } else if (g[i + 1][j - 1]) {
                        g[i][j] = true;
                    }
                }
            }
        }

        vector<int> dp(n, 2000); // s 最长2000
        for (int i = 0; i < n; ++i) {
            if (g[0][i]) { // s[0:i]回文，直接等于0
                dp[i] = 0;
                continue;
            }
            for (int j = 0; j < i; ++j) {
                if (g[j + 1][i]) { // s[j+1:i]是回文，这里才能加1
                    dp[i] = min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n - 1];
    }
};